lib/Mi manual de algoritmos/version_maraton_interuniversitaria_2008-2/src/grafos/ford_fulkerson.tex

   1 % Generator: GNU source-highlight, by Lorenzo Bettini, http://www.gnu.org/software/src-highlite
   2
   3 {\ttfamily \raggedright {
   4 \noindent
   5 \mbox{}\textcolor{ForestGreen}{int}\ cap\textcolor{BrickRed}{[}MAXN\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{][}MAXN\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{],}\ flow\textcolor{BrickRed}{[}MAXN\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{][}MAXN\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{],}\ prev\textcolor{BrickRed}{[}MAXN\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{];} \\
   6 \mbox{} \\
   7 \mbox{}\textit{\textcolor{Brown}{/*}} \\
   8 \mbox{}\textit{\textcolor{Brown}{\ \ cap[i][j]\ =\ Capacidad\ de\ la\ arista\ (i,\ j).}} \\
   9 \mbox{}\textit{\textcolor{Brown}{\ \ flow[i][j]\ =\ Flujo\ actual\ de\ i\ a\ j.}} \\
  10 \mbox{}\textit{\textcolor{Brown}{\ \ prev[i]\ =\ Predecesor\ del\ nodo\ i\ en\ un\ camino\ de\ aumentación.}} \\
  11 \mbox{}\textit{\textcolor{Brown}{\ */}} \\
  12 \mbox{} \\
  13 \mbox{}\textcolor{ForestGreen}{int}\ \textbf{\textcolor{Black}{fordFulkerson}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ n\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ s\textcolor{BrickRed}{,}\ \textcolor{ForestGreen}{int}\ t\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  14 \mbox{}\ \ \textcolor{ForestGreen}{int}\ ans\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
  15 \mbox{}\ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$}n\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\ \textbf{\textcolor{Black}{fill}}\textcolor{BrickRed}{(}flow\textcolor{BrickRed}{[}i\textcolor{BrickRed}{],}\ flow\textcolor{BrickRed}{[}i\textcolor{BrickRed}{]+}n\textcolor{BrickRed}{,}\ \textcolor{Purple}{0}\textcolor{BrickRed}{);} \\
  16 \mbox{}\ \ \textbf{\textcolor{Blue}{while}}\ \textcolor{BrickRed}{(}\textbf{\textcolor{Blue}{true}}\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  17 \mbox{}\ \ \ \ \textbf{\textcolor{Black}{fill}}\textcolor{BrickRed}{(}prev\textcolor{BrickRed}{,}\ prev\textcolor{BrickRed}{+}n\textcolor{BrickRed}{,}\ \textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{);} \\
  18 \mbox{}\ \ \ \ queue\textcolor{BrickRed}{$<$}\textcolor{ForestGreen}{int}\textcolor{BrickRed}{$>$}\ q\textcolor{BrickRed}{;} \\
  19 \mbox{}\ \ \ \ q\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{push}}\textcolor{BrickRed}{(}s\textcolor{BrickRed}{);} \\
  20 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{while}}\ \textcolor{BrickRed}{(}q\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{size}}\textcolor{BrickRed}{()}\ \textcolor{BrickRed}{\&\&}\ prev\textcolor{BrickRed}{[}t\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{==}\ \textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  21 \mbox{}\ \ \ \ \ \ \textcolor{ForestGreen}{int}\ u\ \textcolor{BrickRed}{=}\ q\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{front}}\textcolor{BrickRed}{();} \\
  22 \mbox{}\ \ \ \ \ \ q\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{pop}}\textcolor{BrickRed}{();} \\
  23 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ v\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;}\ v\textcolor{BrickRed}{$<$}n\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}v\textcolor{BrickRed}{)} \\
  24 \mbox{}\ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}v\ \textcolor{BrickRed}{!=}\ s\ \textcolor{BrickRed}{\&\&}\ prev\textcolor{BrickRed}{[}v\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{==}\ \textcolor{BrickRed}{-}\textcolor{Purple}{1}\ \textcolor{BrickRed}{\&\&}\ cap\textcolor{BrickRed}{[}u\textcolor{BrickRed}{][}v\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{$>$}\ \textcolor{Purple}{0}\ \textcolor{BrickRed}{\&\&}\ cap\textcolor{BrickRed}{[}u\textcolor{BrickRed}{][}v\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{-}\ flow\textcolor{BrickRed}{[}u\textcolor{BrickRed}{][}v\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{$>$}\ \textcolor{Purple}{0}\textcolor{BrickRed}{)} \\
  25 \mbox{}\ \ \ \ \ \ \ \ \ \ prev\textcolor{BrickRed}{[}v\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ u\textcolor{BrickRed}{,}\ q\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{push}}\textcolor{BrickRed}{(}v\textcolor{BrickRed}{);} \\
  26 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  27 \mbox{} \\
  28 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}prev\textcolor{BrickRed}{[}t\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{==}\ \textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{)}\ \textbf{\textcolor{Blue}{break}}\textcolor{BrickRed}{;} \\
  29 \mbox{} \\
  30 \mbox{}\ \ \ \ \textcolor{ForestGreen}{int}\ bottleneck\ \textcolor{BrickRed}{=}\ INT$\_$MAX\textcolor{BrickRed}{;} \\
  31 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ v\ \textcolor{BrickRed}{=}\ t\textcolor{BrickRed}{,}\ u\ \textcolor{BrickRed}{=}\ prev\textcolor{BrickRed}{[}v\textcolor{BrickRed}{];}\ u\ \textcolor{BrickRed}{!=}\ \textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{;}\ v\ \textcolor{BrickRed}{=}\ u\textcolor{BrickRed}{,}\ u\ \textcolor{BrickRed}{=}\ prev\textcolor{BrickRed}{[}v\textcolor{BrickRed}{])}\textcolor{Red}{\{} \\
  32 \mbox{}\ \ \ \ \ \ bottleneck\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Black}{min}}\textcolor{BrickRed}{(}bottleneck\textcolor{BrickRed}{,}\ cap\textcolor{BrickRed}{[}u\textcolor{BrickRed}{][}v\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{-}\ flow\textcolor{BrickRed}{[}u\textcolor{BrickRed}{][}v\textcolor{BrickRed}{]);} \\
  33 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  34 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ v\ \textcolor{BrickRed}{=}\ t\textcolor{BrickRed}{,}\ u\ \textcolor{BrickRed}{=}\ prev\textcolor{BrickRed}{[}v\textcolor{BrickRed}{];}\ u\ \textcolor{BrickRed}{!=}\ \textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{;}\ v\ \textcolor{BrickRed}{=}\ u\textcolor{BrickRed}{,}\ u\ \textcolor{BrickRed}{=}\ prev\textcolor{BrickRed}{[}v\textcolor{BrickRed}{])}\textcolor{Red}{\{} \\
  35 \mbox{}\ \ \ \ \ \ flow\textcolor{BrickRed}{[}u\textcolor{BrickRed}{][}v\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{+=}\ bottleneck\textcolor{BrickRed}{;} \\
  36 \mbox{}\ \ \ \ \ \ flow\textcolor{BrickRed}{[}v\textcolor{BrickRed}{][}u\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ \textcolor{BrickRed}{-}flow\textcolor{BrickRed}{[}u\textcolor{BrickRed}{][}v\textcolor{BrickRed}{];} \\
  37 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  38 \mbox{}\ \ \ \ ans\ \textcolor{BrickRed}{+=}\ bottleneck\textcolor{BrickRed}{;} \\
  39 \mbox{}\ \ \textcolor{Red}{\}} \\
  40 \mbox{}\ \ \textbf{\textcolor{Blue}{return}}\ ans\textcolor{BrickRed}{;} \\
  41 \mbox{}\textcolor{Red}{\}} \\
  42
  43 } \normalfont\normalsize